﻿/**	\file		fifo_queue.hpp
 *	\date		(2010-06-02 21:50:59)/(2014-12-28 15:37:00)
 *-----------------------------------------------------------------------------
 *	\version	1.0.1.4
 *	\author		Nick Shallery	(nicknide@gmail.com)
 *	\copyright	YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.
 *-----------------------------------------------------------------------------
**/


#if			!defined(__LOLIX__TOY__FIFO_QUEUE__HPP__NICK__K_IN_G__)
#define		__LOLIX__TOY__FIFO_QUEUE__HPP__NICK__K_IN_G__


#if			!defined(__LOLIX_IMP__LOLIX_LOCK_OPT__H__NICK__K_IN_G__)
	#include	"../imp/lolix_lock_opt.h"
#endif	//	!defined(__LOLIX_IMP__LOLIX_LOCK_OPT__H__NICK__K_IN_G__)

#if			!defined(__LOLIX__LOLI__SIGNAL__H__K_IN_G__)
	#include	"../loli/signal.h"
#endif	//	!defined(__LOLIX__LOLI__SIGNAL__H__K_IN_G__)

#if			!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)
	#include	"../lolix_cfg.h"
#endif	//	!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)

#if			!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)
	#include	"../lolix_type.h"
#endif	//	!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)

#if			!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)
	#include	"./allocator.h"
#endif	//	!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)


namespace lolix{namespace toy{
	namespace _help{
		template<typename _Ty, lolix::ENUM_THREAD_SAFE _E_THREAD, typename _TAlc>
		class _fifo_queue_base;
	}

	template<typename _Ty, lolix::ENUM_THREAD_SAFE _E_THREAD, typename _TAlc>
	class fifo_queue;
}}


template<typename _Ty, typename _TAlc>
class lolix::toy::_help::_fifo_queue_base<_Ty, lolix::THREAD_SAFE_SRW, _TAlc>
{
	CANNT_COPY_LOLI;
	typedef _fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>	this_type;
	struct _T_node
	{
		_T_node(const typename remove_reference<_Ty>::value_type& v):val(v){}

		_Ty			val;
		_T_node*	prev;
		_T_node*	next;
	};
	typedef typename _TAlc::template rebind<_T_node>::other	_TAlc_node;

public:
	typedef typename _TAlc::const_pointer	const_pointer;
	typedef typename _TAlc::const_reference	const_reference;
	typedef typename _TAlc::pointer			pointer;
	typedef typename _TAlc::reference		reference;
	typedef typename _TAlc::size_type		size_type;
	typedef typename _TAlc::value_type		value_type;

	LOLIX_INLINE_CALL _fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>(void)
		: _node(0), _signal(0), _size(0), _alc()
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{}

	template <typename _Alc>
	LOLIX_INLINE_CALL _fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>(_Alc alc)
		: _node(0), _signal(0), _size(0), _alc(alc)
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{}

	LOLIX_INLINE_CALL _fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>(loli::signal* sig)
		: _node(0), _signal(sig), _size(0), _alc()
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{_signal->inc_ref();}

	template <typename _Alc>
	LOLIX_INLINE_CALL _fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>(loli::signal* sig, _Alc alc)
		: _node(0), _signal(sig), _size(0), _alc(alc)
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{_signal->inc_ref();}

	LOLIX_INLINE_CALL ~_fifo_queue_base<_Ty, THREAD_SAFE_SRW, _TAlc>(void)
	{
		_T_node* n = _node;
		while ( n )
		{
			_T_node* cur = n;
			n = n->next;
			_alc.destroy(cur);
			_alc.deallocate(cur, 1);
		}

		if ( _signal )
			_signal->release();

		LOLIX_ASSERT(!_queried_node && !_peeded_node, "存在没有释放完全的请求节点");

	}

	LOLIX_INLINE_CALL bool empty(void)const
	{
		return _size?false:true;
	}

	LOLIX_INLINE_CALL size_type size(void)const
	{
		return _size;
	}

	LOLIX_INLINE_CALL pointer query_node(void)
	{
		_T_node* n = _alc.allocate(1);
#if			LOLIX_CFG__IS_DEBUG
		imp::lock_inc(&_queried_node);
		n->prev = (_T_node*)(0x3aedcfb7);
		n->next = (_T_node*)(0x7aedcfb3);
#endif	//	LOLIX_CFG__IS_DEBUG
		_alc.construct(n);
		return &n->val;
	}

	LOLIX_INLINE_CALL void push_node(pointer node)
	{
		_T_node* n = this->__get_node_from_ptr(node);
		LOLIX_ASSERT(imp::lock_dec(&_queried_node) => 0 && n->next == static_cast<_T_node*>(0x7aedcfb3) && n->prev == static_cast<_T_node*>(0x3aedcfb7)
			, "invalid node count");
		this->__push_node(n);
	}

	LOLIX_INLINE_CALL pointer peek(void)
	{
		_T_node* node_rtv = this->__peek_dat();
		if ( !node_rtv )
			return 0;
#if			LOLIX_CFG__IS_DEBUG
		node_rtv->next = (_T_node*)(0xd4c3b2a1);
		node_rtv->prev = (_T_node*)(0x4d3c2b1a);
		imp::lock_inc(&_peeded_node);
#endif	//	LOLIX_CFG__IS_DEBUG
		return &node_rtv->val;
	}

	LOLIX_INLINE_CALL void free(pointer r)
	{
		if ( !r )
			return;
		_T_node* node = this->__get_node_from_ptr(r);
#if			LOLIX_CFG__IS_DEBUG
		LOLIX_ASSERT(node->next == (_T_node*)(0xd4c3b2a1), "invalid pointer");
		LOLIX_ASSERT(node->prev == (_T_node*)(0x4d3c2b1a), "invalid pointer");
		LOLIX_ASSERT(imp::lock_dec(&_peeded_node) >= 0, "invalid pointer node");
#endif	//	LOLIX_CFG__IS_DEBUG
		_alc.destroy(node);
		_alc.deallocate(node, 1);
	}

	LOLIX_INLINE_CALL void push(const value_type& v)
	{
		_T_node* n = _alc.allocate(1);
		_alc.construct(n, _T_node(v));
		this->__push_node(n);
	}


	LOLIX_INLINE_CALL bool pop(pointer r)
	{
		_T_node* n = this->__peek_dat();
		if ( !n )
			return false;
		lolix::discard_copy(*r, n->val);
		_alc.destroy(n);
		_alc.deallocate(n, 1);
		return true;
	}

private:
	LOLIX_INLINE_CALL _T_node* __peek_dat(void)
	{
		if ( !_size )
			return 0;

		--_size;
		_T_node* n = _node;
		_T_node* next = _node->next;
		_T_node* prev = _node->prev;
		prev->next = next;
		next->prev = prev;
		return n;
	}

	LOLIX_INLINE_CALL _T_node* __get_node_from_ptr(pointer r)
	{
		ptrdiff_t node_ptr = r;
		_T_node* n = static<_T_node*>(node_ptr - LOLIX_OFFSET_OF(_T_node, val));
		return n;
	}

	LOLIX_INLINE_CALL void __push_node(_T_node* n)
	{
		++_size;
		if ( !_node )
		{
			_node = n;
			n->next = n;
			n->prev = n;
			if ( _signal )
				_signal->set();
		}
		else
		{
			n->next = _node;
			n->prev = _node->prev;
			n->prev->next = n;
			n->next->perv = n;
		}
	}

	_T_node*		_node;
	loli::signal*	_signal;
	size_type		_size;
	_TAlc_node		_alc;
#if			LOLIX_CFG__IS_DEBUG
	lolix::ptrdiff_type	_queried_node;
	lolix::ptrdiff_type _peeded_node;
#endif	//	LOLIX_CFG__IS_DEBUG
};


template<typename _Ty, typename _TAlc>
class lolix::toy::_help::_fifo_queue_base<_Ty, lolix::THREAD_SAFE_SRMW, _TAlc>
{
	CANNT_COPY_LOLI;
	typedef _fifo_queue_base<_Ty, THREAD_SAFE_SRMW, _TAlc>	this_type;
	struct _T_node
	{
		LOLIX_INLINE_CALL _T_node(void){}
		LOLIX_INLINE_CALL _T_node(typename remove_reference<_Ty>::type const& v):val(v){}

		_Ty			val;
		_T_node*	next;
	};
	typedef typename _TAlc::template rebind<_T_node>::other	_TAlc_node;
	typedef typename _TAlc::template rebind<_Ty>::other _TAlcVal;

public:
	typedef _TAlc_node	allocator_type;
	typedef typename _TAlcVal::const_pointer	const_pointer;
	typedef typename _TAlcVal::const_reference	const_reference;
	typedef typename _TAlcVal::pointer			pointer;
	typedef typename _TAlcVal::reference		reference;
	typedef typename _TAlcVal::size_type		size_type;
	typedef typename _TAlcVal::value_type		value_type;

	LOLIX_INLINE_CALL _fifo_queue_base(void)
		: _send(0), _recv(0), _signal(0), _alc()
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{
	}

	template <typename _Alc>
	LOLIX_INLINE_CALL explicit _fifo_queue_base(_Alc alc)
		: _send(0), _recv(0), _signal(0), _alc(alc)
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{
	}

	LOLIX_INLINE_CALL explicit _fifo_queue_base(loli::signal* sig)
		: _send(0), _recv(0), _signal(sig), _alc()
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{
		if ( _signal )
			_signal->inc_ref();
	}

	template <typename _Alc>
	LOLIX_INLINE_CALL _fifo_queue_base(loli::signal* sig, _Alc alc)
		: _send(0), _recv(0), _signal(sig), _alc(alc)
#if			LOLIX_CFG__IS_DEBUG
		, _queried_node(0)
		, _peeded_node(0)
#endif	//	LOLIX_CFG__IS_DEBUG
	{
		if ( _signal )
			_signal->inc_ref();
	}

	LOLIX_INLINE_CALL ~_fifo_queue_base(void)
	{
		_T_node* ns[] = {_send, _recv};
		for ( size_type i = 0; i != ARRAY_SIZE(ns); ++i )
		{
			_T_node* n = ns[i];
			while ( n )
			{
				_T_node* cur = n;
				n = n->next;
				_alc.destroy(cur);
				_alc.deallocate(cur, 1);
			}
		}

		if ( _signal )
			_signal->release();
		LOLIX_ASSERT(!_queried_node && !_peeded_node, "queried node not return");
	}

	LOLIX_INLINE_CALL bool empty(void)const
	{
		return !_send && !_recv;
	}

	LOLIX_INLINE_CALL pointer query_node(void)
	{
		_T_node* n = _alc.allocate(1);
#if			LOLIX_CFG__IS_DEBUG
		imp::lock_inc(&_queried_node);
		n->next = (_T_node*)(0x9aedcfb0);
#endif	//	LOLIX_CFG__IS_DEBUG
		_alc.construct(n);
		return &n->val;
	}

	LOLIX_INLINE_CALL void push_node(pointer node)
	{
		_T_node* n = this->__get_node_from_ptr(node);
		LOLIX_ASSERT(imp::lock_dec(&_queried_node) >= 0 && n->next == (_T_node*)(0x9aedcfb0)
			, "invalid node count");
		this->__push_node(n);
	}

	LOLIX_INLINE_CALL void push(const value_type& v)
	{
		_T_node* n = _alc.allocate(1);
		_alc.construct(n, _T_node(v));
		this->__push_node(n);
	}

#if			LOLIX_CFG__SUPPORT_CPP_0X
	LOLIX_INLINE_CALL void push(value_type&& v)
	{
		_T_node* n = _alc.allocate(1);
		_alc.construct(n, _T_node(forward<value_type>(v)));
		this->__push_node(n);
	}

#endif	//	LOLIX_CFG__SUPPORT_CPP_0X


	LOLIX_INLINE_CALL pointer peek(void)
	{
		_T_node* node_rtv = this->__peek_dat();
		if ( !node_rtv )
			return 0;
#if			LOLIX_CFG__IS_DEBUG
		node_rtv->next = (_T_node*)(0x1a2b3c4d);
		imp::lock_inc(&_peeded_node);
#endif	//	LOLIX_CFG__IS_DEBUG
		return &node_rtv->val;
	}

	LOLIX_INLINE_CALL void free(pointer r)
	{
		if ( !r )
			return;
		_T_node* node = this->__get_node_from_ptr(r);
#if			LOLIX_CFG__IS_DEBUG
		LOLIX_ASSERT(node->next == (_T_node*)(0x1a2b3c4d) && imp::lock_dec(&_peeded_node) >= 0, "invalid pointer");
#endif	//	LOLIX_CFG__IS_DEBUG
		_alc.destroy(node);
		_alc.deallocate(node, 1);
	}

	LOLIX_INLINE_CALL bool pop(pointer r)
	{
		if ( !_recv && !__peek_dat() )
			return false;

		lolix::discard_copy(*r, _recv->val);
		_T_node* ptr = _recv;
		_recv = _recv->next;
		_alc.destroy(ptr);
		_alc.deallocate(ptr, 1);
		return true;
	}

protected:
	_T_node* __get_node_from_ptr(pointer node)
	{
		ptrdiff_t node_ptr = (ptrdiff_t)node;
		_T_node* n = (_T_node*)(node_ptr - LOLIX_OFFSET_OF(_T_node, val));
		return n;
	}

	LOLIX_INLINE_CALL _T_node* __peek_dat()
	{
		if ( !_recv )
		{
			_T_node* start = imp::lock_chg(&_send, 0);
			_T_node* prev = start;
			if ( !prev )
				return 0;
			//	逆序排列
			_T_node* next = prev->next;
			while ( next )
			{
				_T_node* n = next->next;
				next->next = prev;
				prev = next;
				next = n;
			}

			start->next = 0;
			_recv = prev;
		}

		_T_node* rtv = _recv;
		_recv = _recv->next;
		return rtv;
	}

	LOLIX_INLINE_CALL void __push_node(_T_node* n)
	{
		if ( this->__push_node_ptr(&this->_send, n) && _signal )
			this->_signal->set();
	}

	LOLIX_INLINE_CALL bool __push_node_ptr(_T_node** tgt, _T_node* n)
	{
		_T_node* next;
		do
		{
			n->next = next = *tgt;
		}while ( imp::lock_cchg(tgt, n, n->next) != next );
		return next == 0;
	}

	_T_node*			_send;
	_T_node*			_recv;
	loli::signal*		_signal;
#if			LOLIX_CFG__IS_DEBUG
	lolix::ptrdiff_type _queried_node;
	lolix::ptrdiff_type _peeded_node;
#endif	//	LOLIX_CFG__IS_DEBUG
	_TAlc_node	_alc;
};


template<typename _Ty, typename _TAlc>
class lolix::toy::_help::_fifo_queue_base<_Ty, lolix::THREAD_SAFE_SRSW, _TAlc>
	:private lolix::toy::_help::_fifo_queue_base<_Ty, THREAD_SAFE_SRMW, _TAlc>
{
	CANNT_COPY_LOLI;
	typedef _fifo_queue_base<_Ty, THREAD_SAFE_SRSW, _TAlc>	this_type;
	typedef _fifo_queue_base<_Ty, THREAD_SAFE_SRMW, _TAlc>	base_type;
public:
	typedef typename base_type::const_pointer	const_pointer;
	typedef typename base_type::const_reference	const_reference;
	typedef typename base_type::pointer			pointer;
	typedef typename base_type::reference		reference;
	typedef typename base_type::size_type		size_type;
	typedef typename base_type::value_type		value_type;

	template <typename _TyP>
	LOLIX_INLINE_CALL explicit _fifo_queue_base(_TyP p0) : base_type(p0){ }
	template <typename _Typ0, typename _Typ1>
	LOLIX_INLINE_CALL _fifo_queue_base(_Typ0 p0, _Typ1 p1) : base_type(p0, p1){ }
	using base_type::empty;
	using base_type::push;
	using base_type::pop;
	using base_type::query_node;
	using base_type::push_node;
	using base_type::peek;
	using base_type::free;
};


template<typename _Ty, lolix::ENUM_THREAD_SAFE _E_THREAD, typename _TAlc>
class lolix::toy::fifo_queue
	: private _help::_fifo_queue_base<_Ty, _E_THREAD, typename _TAlc::template rebind<_Ty>::other>
{
	CANNT_COPY_LOLI;
	typedef fifo_queue<_Ty, _E_THREAD, _TAlc>	this_type;
	typedef _help::_fifo_queue_base<_Ty, _E_THREAD, typename _TAlc::template rebind<_Ty>::other>	base_type;
public:
	typedef typename base_type::const_pointer	const_pointer;
	typedef typename base_type::const_reference	const_reference;
	typedef typename base_type::pointer			pointer;
	typedef typename base_type::reference		reference;
	typedef typename base_type::size_type		size_type;
	typedef typename base_type::value_type		value_type;

	template <typename _TyP>
	LOLIX_INLINE_CALL explicit fifo_queue(_TyP p0) : base_type(p0){ }
	template <typename _Typ0, typename _Typ1>
	LOLIX_INLINE_CALL fifo_queue(_Typ0 p0, _Typ1 p1) : base_type(p0, p1){ }
	using base_type::empty;
	using base_type::push;
	using base_type::pop;
	using base_type::query_node;
	using base_type::push_node;
	using base_type::peek;
	using base_type::free;
};


#endif	//	!defined(__LOLIX__TOY__FIFO_QUEUE__HPP__NICK__K_IN_G__)
